翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク reconstruction conjecture ： ウィキペディア英語版 reconstruction conjecture Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly〔Kelly, P. J., (A congruence theorem for trees ), ''Pacific J. Math.'' 7 (1957), 961–968.〕 and Ulam.〔Ulam, S. M., A collection of mathematical problems, Wiley, New York, 1960.〕 ==Formal statements== Given a graph $G\; =\; (V,E)$, a vertex-deleted subgraph of $G$ is a subgraph formed by deleting exactly one vertex from $G$. Clearly, it is an induced subgraph of $G$. For a graph $G$, the deck of G, denoted $D(G)$, is the multiset of all vertex-deleted subgraphs of $G$. Each graph in $D(G)$ is called a card. Two graphs that have the same deck are said to be hypomorphic. With these definitions, the conjecture can be stated as: * Reconstruction Conjecture: Any two hypomorphic graphs on at least three vertices are isomorphic. : (The requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks.) Harary〔Harary, F., On the reconstruction of a graph from a collection of subgraphs. In ''Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963)''. Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 47–52.〕 suggested a stronger version of the conjecture: * Set Reconstruction Conjecture: Any two graphs on at least four vertices with the same sets of vertex-deleted subgraphs are isomorphic. Given a graph $G\; =\; (V,E)$, an edge-deleted subgraph of $G$ is a subgraph formed by deleting exactly one edge from $G$. For a graph $G$, the edge-deck of G, denoted $ED(G)$, is the multiset of all edge-deleted subgraphs of $G$. Each graph in $ED(G)$ is called an edge-card. * Edge Reconstruction Conjecture: (Harary, 1964)〔 Any two graphs with at least four edges and having the same edge-decks are isomorphic. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「reconstruction conjecture」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.